/**
 * @file   Merge.cpp
 * @author xingyifan
 * @date   2021/08/21 15:38:57
 * 
 * @brief  merge sort
 * 
 * 
 */

#include "Merge.h"

//归并两个部分[a,b),[b,c)
void Merge(double A[], int a, int b, int c)
{
    //记录两个数组的开头
    int ab_id = 0;
    int bc_id = 0;
    //记录最大值
    double max = 0;

    //定义两个数组
    double AB[b - a + 1];
    double BC[c - b + 1];

    for (int i = a; i < b; i++)
    {
        AB[i - a] = A[i];
        max = MAX(max, A[i]) + 1;
    }

    for (int i = b; i < c; i++)
    {
        BC[i - b] = A[i];
        max = MAX(max, A[i]) + 1;
    }

    //最后一位存放最小值，用作边界
    AB[b - a] = BC[c - b] = max;

    for (int i = a; i < c; i++)
    {
        if (AB[ab_id] < BC[bc_id])
        {
            A[i] = AB[ab_id];
            ab_id++;
        }
        else
        {
            A[i] = BC[bc_id];
            bc_id++;
        }
    }
}

//归并排序
void Merge_Sort(double A[], int a, int b)
{
    if (b > a + 1)
    {
        int mid = (a + b) / 2;
        Merge_Sort(A, a, mid);
        Merge_Sort(A, mid, b);
        Merge(A, a, mid, b);
    }
}

void Merge_Sort(int n, double A[])
{
    Merge_Sort(A, 0, n);
    for (int i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
}